#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
栈（Stack）的完整实现
包含基本操作：push, pop, peek, is_empty, size
以及一些实际应用示例
"""

class Stack:
    """栈类实现"""
    
    def __init__(self):
        """初始化空栈"""
        self.items = []
    
    def push(self, item):
        """
        入栈操作
        Args:
            item: 要入栈的元素
        """
        self.items.append(item)
        print(f"入栈: {item}")
    
    def pop(self):
        """
        出栈操作
        Returns:
            栈顶元素
        Raises:
            IndexError: 当栈为空时抛出异常
        """
        if not self.is_empty():
            item = self.items.pop()
            print(f"出栈: {item}")
            return item
        raise IndexError("栈为空，无法出栈")
    
    def peek(self):
        """
        查看栈顶元素（不删除）
        Returns:
            栈顶元素
        Raises:
            IndexError: 当栈为空时抛出异常
        """
        if not self.is_empty():
            return self.items[-1]
        raise IndexError("栈为空，无法查看栈顶")
    
    def is_empty(self):
        """
        判断栈是否为空
        Returns:
            bool: True表示空，False表示非空
        """
        return len(self.items) == 0
    
    def size(self):
        """
        获取栈的大小
        Returns:
            int: 栈中元素个数
        """
        return len(self.items)
    
    def clear(self):
        """清空栈"""
        self.items.clear()
        print("栈已清空")
    
    def __str__(self):
        """字符串表示"""
        return f"Stack({self.items})"
    
    def __len__(self):
        """长度表示"""
        return len(self.items)


def test_basic_operations():
    """测试基本操作"""
    print("=" * 50)
    print("测试栈的基本操作")
    print("=" * 50)
    
    stack = Stack()
    
    # 测试空栈
    print(f"栈是否为空: {stack.is_empty()}")
    print(f"栈的大小: {stack.size()}")
    
    # 入栈操作
    print("\n--- 入栈操作 ---")
    stack.push(1)
    stack.push(2)
    stack.push(3)
    stack.push("hello")
    stack.push([4, 5, 6])
    
    print(f"当前栈: {stack}")
    print(f"栈的大小: {stack.size()}")
    print(f"栈顶元素: {stack.peek()}")
    
    # 出栈操作
    print("\n--- 出栈操作 ---")
    while not stack.is_empty():
        try:
            stack.pop()
            print(f"当前栈: {stack}")
        except IndexError as e:
            print(f"错误: {e}")
    
    print(f"栈是否为空: {stack.is_empty()}")


def test_parentheses_matching():
    """测试括号匹配"""
    print("\n" + "=" * 50)
    print("测试括号匹配功能")
    print("=" * 50)
    
    def is_valid_parentheses(s: str) -> bool:
        """检查括号是否匹配"""
        stack = []
        brackets = {')': '(', '}': '{', ']': '['}
        
        for char in s:
            if char in '({[':
                stack.append(char)
            elif char in ')}]':
                if not stack or stack.pop() != brackets[char]:
                    return False
        
        return len(stack) == 0
    
    # 测试用例
    test_cases = [
        "()",
        "()[]{}",
        "(]",
        "([)]",
        "{[]}",
        "((()))",
        "(()",
        ""
    ]
    
    for test_case in test_cases:
        result = is_valid_parentheses(test_case)
        print(f"'{test_case}' -> {'✓' if result else '✗'}")


def test_reverse_polish_notation():
    """测试逆波兰表达式求值"""
    print("\n" + "=" * 50)
    print("测试逆波兰表达式求值")
    print("=" * 50)
    
    def eval_rpn(tokens: list) -> int:
        """计算逆波兰表达式的值"""
        stack = []
        operators = {'+', '-', '*', '/'}
        
        for token in tokens:
            if token not in operators:
                stack.append(int(token))
            else:
                b = stack.pop()
                a = stack.pop()
                if token == '+':
                    stack.append(a + b)
                elif token == '-':
                    stack.append(a - b)
                elif token == '*':
                    stack.append(a * b)
                elif token == '/':
                    stack.append(int(a / b))
        
        return stack[0]
    
    # 测试用例
    test_cases = [
        (["2", "1", "+", "3", "*"], 9),      # (2+1)*3 = 9
        (["4", "13", "5", "/", "+"], 6),     # 4 + (13/5) = 6
        (["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"], 22)
    ]
    
    for tokens, expected in test_cases:
        result = eval_rpn(tokens)
        print(f"{tokens} = {result} {'✓' if result == expected else '✗'}")


def test_text_editor():
    """测试文本编辑器的撤销重做功能"""
    print("\n" + "=" * 50)
    print("测试文本编辑器撤销重做功能")
    print("=" * 50)
    
    class TextEditor:
        def __init__(self):
            self.content = ""
            self.undo_stack = []
            self.redo_stack = []
        
        def type_text(self, text):
            """输入文本"""
            self.undo_stack.append(self.content)
            self.content += text
            self.redo_stack.clear()  # 新操作会清空重做栈
            print(f"输入: '{text}' -> 内容: '{self.content}'")
        
        def undo(self):
            """撤销操作"""
            if self.undo_stack:
                self.redo_stack.append(self.content)
                self.content = self.undo_stack.pop()
                print(f"撤销 -> 内容: '{self.content}'")
            else:
                print("无法撤销，没有更多操作")
        
        def redo(self):
            """重做操作"""
            if self.redo_stack:
                self.undo_stack.append(self.content)
                self.content = self.redo_stack.pop()
                print(f"重做 -> 内容: '{self.content}'")
            else:
                print("无法重做，没有更多操作")
        
        def get_content(self):
            return self.content
    
    # 测试文本编辑器
    editor = TextEditor()
    
    editor.type_text("Hello")
    editor.type_text(" World")
    editor.type_text("!")
    
    print(f"\n当前内容: '{editor.get_content()}'")
    
    editor.undo()
    editor.undo()
    editor.redo()
    editor.redo()
    
    print(f"最终内容: '{editor.get_content()}'")


def main():
    """主函数"""
    print("栈（Stack）数据结构演示程序")
    print("=" * 50)
    
    # 运行所有测试
    test_basic_operations()
    test_parentheses_matching()
    test_reverse_polish_notation()
    test_text_editor()
    
    print("\n" + "=" * 50)
    print("所有测试完成！")
    print("=" * 50)


if __name__ == "__main__":
    main()
